import java.util.*;

/**
 * 1743. 从相邻元素对还原数组
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
 */
public class Solutions_1743 {
    public static void main(String[] args) {
        int[][] adjacentPairs1 = {{2, 1}, {3, 4}, {3, 2}};  // output: {1, 2, 3, 4}
        int[][] adjacentPairs2 = {{4, -2}, {1, 4}, {-3, 1}};  // output: {-2, 4, 1, -3}
        int[][] adjacentPairs3 = {{100000, -100000}};  // output: {100000, -100000}

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(adjacentPairs1);
        inputs.add(adjacentPairs2);
        inputs.add(adjacentPairs3);

        for (int[][] input : inputs) {
            int[] result = restoreArray(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 解题思路：贪心算法
     * 1. 找到端点元素
     * 2. 通过端点元素，依次推导出下一元素
     * 3. 完成构建
     *
     * 优化点：
     * 通过 nodeSum 数组来记录某一个节点的相邻节点的元素和
     * 通过 visited 数组来记录某一个节点的出现次数（出现两次为 false，出现一次为 true）
     * 以 {{2, 1}, {3, 4}, {3, 2}} 为例：
     * visited[1] = true     nodeSum[1] = 2
     * visited[2] = false    nodeSum[2] = 4
     * visited[3] = false    nodeSum[3] = 6
     * visited[4] = true     nodeSum[4] = 3
     *
     * 首先找到端点元素 1
     * 而 nodeSum[1] = 2，即相邻节点就是 2
     * 下一元素为 2，同时 nodeSum[2] 需要减 1（因为相邻节点 1 已经使用了）
     *
     * 元素为 2 时
     * nodeSum[2] = 3，即相邻节点就是 3
     * 下一元素为 3，同时 nodeSum[3] 需要减 2（因为相邻节点 2 已经使用了）
     *
     * 元素为 3 时
     * nodeSum[3] = 4，即相邻节点就是 4
     * 下一元素为 4，同时 nodeSum[4] 需要减 3（因为相邻节点 3 已经使用了）
     *
     */
    public static int[] restoreArray(int[][] adjacentPairs) {
        int len = adjacentPairs.length;
        // 共有 count 个元素
        int count = len + 1;
        int[] res = new int[count];
        // visited[100001] = true，说明节点 1 已经被添加到了结果集中（即不能再使用）
        boolean[] visited = new boolean[2 * 100000 + 1];
        // nodeSum[100001] = 5，节点 1 的左右相邻节点的和为 5（也有可能只有一个相邻节点，就是 5）
        int[] nodeSum = new int[2 * 100000 + 1];

        for (int[] arr : adjacentPairs) {
            int node1 = arr[0], node2 = arr[1];
            // 在 adjacentPairs 中只出现了一次的元素，最终为 true，即为两侧端点上的元素
            // 若出现了两次，最终 visited[node] 为 false，即不为两侧端点上的元素
            visited[node1 + 100000] = !visited[node1 + 100000];
            visited[node2 + 100000] = !visited[node2 + 100000];

            nodeSum[node1 + 100000] += node2;
            nodeSum[node2 + 100000] += node1;
        }
        // 找到任意一个端点元素
        int cur = -1;
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) {
                cur = i - 100000;
                break;
            }
        }

        int idx = 0;
        while (idx < count) {
            res[idx] = cur;
            // 由当前元素可以计算出相邻的一个节点
            int next = nodeSum[cur + 100000];
            // next 节点的 nodeSum 减去 cur（因为 cur 已经使用了）
            nodeSum[next + 100000] -= cur;

            cur = next;
            idx ++;
        }
        return res;
    }
}
